package Combination_Sum



/*
回溯算法：
1：深度优先搜索，递归调用，需要传递起始的切片，路径，目标值，选择的值的下标。
2：之所以记录选择值的下标，防止相同数字，不同排序。
 */

var res [][]int
func combinationSum(candidates []int, target int) [][]int {
	if len(candidates) == 0 {
		return [][]int{}
	}
	res = make([][]int , 0)
	backtrace(candidates , make([]int , 0) , target , 0)
	return res
}




func backtrace (candidates []int , pathnums []int , target int , num int ) {
	tmp := 0
	for _ , v := range pathnums {
		tmp = tmp + v
	}
	if tmp > target {
		return
	}
	if tmp == target {
		tres := make([]int , len(pathnums))
		copy(tres , pathnums)
		res = append(res , tres)
	}
	for i:= num ; i < len(candidates) ; i ++ {
		pathnums = append(pathnums , candidates[i])
		backtrace(candidates , pathnums  ,target , i)
		pathnums = pathnums[:len(pathnums) - 1]
	}
}
